//
//  Intersect.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/13.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  350. 两个数组的交集 II

import UIKit

/*
 350. 两个数组的交集 II
 给定两个数组，编写一个函数来计算它们的交集。

 示例 1:

 输入: nums1 = [1,2,2,1], nums2 = [2,2]
 输出: [2,2]
 
 
 示例 2:

 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 输出: [4,9]
 说明：

 ---输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。（描述似乎有误）
 
 对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
 我们可以不考虑输出结果的顺序。
 进阶:

 如果给定的数组已经排好序呢？你将如何优化你的算法？
 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
 */

class Intersect: NSObject {
    
    //双指针法
    func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        
        if nums1.count == 0 || nums2.count == 0{
            return []
        }
        
        var resultArr:[Int] = []

        //需要先排序
        let nums1 = nums1.sorted()
        let nums2 = nums2.sorted()
        
        var i = 0
        var j = 0
        
        while i < nums1.count && j < nums2.count {
            if nums1[i] == nums2[j] {
                resultArr.append(nums1[i])
                print("num1[\(i)] == nums[\(j)],加入结果")

                i += 1
                j += 1
            }else if nums1[i] < nums2[j] {
                i += 1
            }else if nums1[i] > nums2[j] {
                j += 1
            }
        }
        
        return resultArr
    }
    
    
    //哈希表法
    /*
     首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，
     如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

     为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。

     */
    func intersect2(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        
        if nums1.count > nums2.count {
            //先遍历较短的
            return self.intersect2(nums2, nums1)
        }
        
        var resultArr:[Int] = []
        var firArrDic:[Int:Int] = [:]
        
        for ele in nums1{
            if firArrDic[ele] != nil {
                firArrDic[ele]! += 1
            }else{
                firArrDic[ele] = 1
            }
        }
        
        for ele2 in nums2{
            if firArrDic[ele2] != nil{
                
//                if firArrDic[ele2]! > 0 {
//                    firArrDic[ele2] = firArrDic[ele2]! - 1
//                    resultArr.append(ele2)
//                }

                //比上面快8ms
                firArrDic[ele2] = firArrDic[ele2]! - 1
                if firArrDic[ele2]! >= 0 {
                    resultArr.append(ele2)
                }
                
            }
        }
        
        return resultArr
    }
    
}
